home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2617 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.8 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: quick decision: is n a power of 2?
  5. Date: 22 Jan 1996 09:09:55 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4e0gd3INNa7s@keats.ugrad.cs.ubc.ca>
  8. References: <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca> <4dpian$gij@oxy.rust.net> <4drjkc$il4@news.gate.net>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4drjkc$il4@news.gate.net>, William Hutto <bhutto@gate.net> wrote:
  12.  >In article <4dpian$gij@oxy.rust.net>, ebennett@rust.net spake:
  13.  >;Bill Simpson <wsimpson@uwinnipeg.ca> wrote:
  14.  >;
  15.  >;>Is there a fast way to decide whether a number n is a power of 2?
  16.  >;
  17.  >;
  18.  >;Working with positive numbers, a number will be a power of 2 if there
  19.  >;is exactly one bit set in the number.  (For negative numbers, you can
  20.  >;use the following by taking the abs() of the number).
  21.  >
  22.  >Negative numbers? The person in question wasn't asking for a power of -2. 
  23.  >Power of 2 has to be > 0 for integers.
  24.  >
  25.  >;
  26.  >;Given some number, there is a neat trick to generate a mask which will
  27.  >;have exactly one bit set in it.  The bit set will be the least
  28.  >;significant non-zero bit in the original number:
  29.  >;
  30.  >;    mask = ~number & number;
  31.  >
  32.  >It's faster just to use:
  33.  >
  34.  >mask = 0;
  35.  >
  36.  >;
  37.  >;Now, if number contained a single non-zero bit (and is therefore a
  38.  >;power of 2),  mask will be equal to number.  Therefore:
  39.  >;
  40.  >;   if (number == (~number & number))
  41.  
  42. Umm, the bitwise AND is very much like the AND in truth functional logic.
  43.  
  44. A statement like "I'm a newbie and I'm not a newbie" is called a contradiction
  45. because it is always false. Analogously, taking a bitwise complement of a
  46. number and AND'ing it with the original always produces zero.
  47.  
  48. A:    0100
  49. ~A:    1011
  50. ------------
  51. A ^ ~A: 0000
  52.  
  53. -- 
  54.  
  55.